class Solution(object):
    def findStrobogrammatic(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        def search(k):
            if k == 1:
                return ['0', '1', '8']
            else:
                if k == 2:
                    out = ['11', '88', '69', '96']
                    if k < n:
                        out.append('00')
                    return out
                else:
                    suffix = search(k - 2)
                    out = []
                    for item in suffix:
                        out.append('1' + item + '1')
                        out.append('8' + item + '8')
                        out.append('6' + item + '9')
                        out.append('9' + item + '6')
                        if k < n:
                            out.append('0' + item + '0')
                    return out
        return search(n)

data = Solution()
n = 2
print(data.findStrobogrammatic(n))
